/**
 * 快速排序
 */
#include <iostream>
#include <vector>

using namespace std;

// 分区函数：返回锚点
int partition(vector<int> &a, int l, int r)
{
    int nIdx = l + rand() % (r - l + 1); // 在l到r之间找随机一个脚标！
    swap(a[l], a[nIdx]);                 // 交换最左侧的值和当前随机脚标的值
    int i = l, j = r;                    // 定义两个游标
    int x = a[i];                        // 确定为交换之后的最左边的值
    while (i < j)
    {
        // 处理大于x的部分
        while (i < j && a[j] > x)
        { // 希望j右边部分都大于x（弹出条件就是右边不如左边大了）
            j--;
        }
        if (i < j)
        { // 如果右边没有左边大了之后，交换大值和右边的值，然后向右移动左边的脚标值
            swap(a[i], a[j]);
            ++i;
        }
        // 小于x的部分
        while (i < j && a[i] < x)
        { // 希望i右边都小于x（弹出条件就是右边比左边大了）
            i++;
        }
        if (i < j)
        { // 如果右边比左边大，交换到右边，然后左移右边的脚标值
            swap(a[i], a[j]);
            --j;
        }
    }
    a[i] = x; // 之前的值要赋值到现在的位置上
    return i; //
}

void quickSort(vector<int> &a, int l, int r)
{
    if (l >= r)
    {
        return;
    }
    int nPivot = partition(a, l, r); // 锚点：保证左边小，右边大
    quickSort(a, l, nPivot - 1);
    quickSort(a, nPivot + 1, r);
}

int main()
{
    vector<int> arr = {10, 7, 8, 9, 1, 5};
    int n = arr.size();

    cout << "Original array: ";
    for (int num : arr)
    {
        cout << num << " ";
    }
    cout << endl;

    quickSort(arr, 0, n - 1);

    cout << "Sorted array: ";
    for (int num : arr)
    {
        cout << num << " ";
    }
    cout << endl;
    return 0;
}